import sun.security.krb5.internal.APRep;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-11
 * Time: 22:41
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class BSTIterator {
    // 多定义的一个头节点, 方便后面的 函数调用, 这里比较巧
    public TreeNode head = new TreeNode(-1);
    public BSTIterator(TreeNode root) {
        morris(root);
    }

    public void morris(TreeNode root){
        TreeNode prev = head;
        TreeNode before = head;
        while (root != null){
            prev = root.left;
            while (prev != null && prev.right != null && prev.right != root){
                prev = prev.right;
            }
            if(prev == null || prev.right == root){
                // 均说明左子树已经遍历完了, 该遍历右子树了
                // 关键节点就是记录了前一个节点的位置, 从而能够线索化
                // 先线索化
                before.right = root;
                // 移动前一个节点
                before = root;
                // 左子树统一置为空, 当然也可以不置空, 因为就没有用到左子树
                root.left = null;
                // 开始遍历右子树
                root = root.right;
            }else{
                // 左子树还没有遍历
                // 先标记一下, 左子树已经遍历过了
                prev.right = root;
                // 开始遍历
                root = root.left;
            }
        }
    }


    public int next() {
        head = head.right;
        return head.val;
    }

    public boolean hasNext() {
        return head.right != null;
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(7);
        TreeNode c = new TreeNode(9);
        TreeNode d = new TreeNode(15);
        TreeNode e = new TreeNode(20);
        b.left = a;
        b.right = d;
        d.left = c;
        d.right = e;
        BSTIterator bstIterator=new BSTIterator(b);
        bstIterator.next();    // 返回 3
        bstIterator.next();    // 返回 7
        bstIterator.hasNext(); // 返回 True
        bstIterator.next();    // 返回 9
        bstIterator.hasNext(); // 返回 True
        bstIterator.next();    // 返回 15
        bstIterator.hasNext(); // 返回 True
        bstIterator.next();    // 返回 20
        bstIterator.hasNext(); // 返回 False
    }
}
